#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <unistd.h>
#include <string.h>
#include <strings.h>
#include <time.h>

#define SIZE 20

typedef int datatype;

struct node
{
    datatype data;
    struct node *next;
};

typedef struct
{
    unsigned long table_size;
    struct node **table_entry;

}hash_table;

void show(hash_table *ht, unsigned long pos, datatype data);

hash_table *init_ht(unsigned long size)
{
    hash_table *ht = malloc(sizeof(hash_table));
    ht->table_size = size;
    ht->table_entry = calloc(size, sizeof(struct node *));

    return ht;
}

void hash_add(datatype data, hash_table *ht)
{
    // 使用保留除数法，获得哈希地址（即数组的下标值）
    unsigned long hash_addr = data % (SIZE-1);

    struct node *new = malloc(sizeof(struct node));
    new->data = data;
    new->next = NULL;

    show(ht, hash_addr, data);
    printf("=================================\n");

    // 1：该哈希地址可用，直接将新节点放进去
    if(ht->table_entry[hash_addr] == NULL)
    {
        ht->table_entry[hash_addr] = new;
    }
    // 2：该哈希地址不可用，将新节点链到冲突链表的末尾
    else
    {
        struct node *p = ht->table_entry[hash_addr];
        while(p->next != NULL)
        {
            p = p->next;
        }
        p->next = new;
    }
}

bool hash_del(datatype data, hash_table *ht)
{
    // 使用保留除数法，获得哈希地址（即数组的下标值）
    unsigned long hash_addr = data % (SIZE-1);

    // 1：该哈希地址为空，代表无此节点
    if(ht->table_entry[hash_addr] == NULL)
        return false;

    // 2：该哈希地址不为空，则在冲突链表中试图删除data
    else
    {
        struct node *p = ht->table_entry[hash_addr];

        // 2.1 data是链表的首个节点
        if(p->data == data)
        {
            ht->table_entry[hash_addr] = p->next;
            free(p);
            return true;
        }

        // 2.2 data不存在
        while(p!=NULL && p->data != data)
        {
            p = p->next;
        }
        if(p == NULL)
            return false;

        // 2.3 data存在且链表不止一个节点
        struct node *q;
        for(q=ht->table_entry[hash_addr];
            q->next != p; q=q->next);
        q->next = p->next;
        free(p);
        return true;
    }
}

void show(hash_table *ht, unsigned long pos, datatype data)
{
    struct node *p;

    int i;
    for(i=0; i<ht->table_size; i++)
    {
        p = ht->table_entry[i];

        printf("table_entry[%d]: ", i);

        if(p != NULL)
        {
            struct node *q = p;
            while(q != NULL)
            {
                printf("%d\t", q->data);
                q = q->next;
            }
        }
    
        if(pos == i)
        {
            printf("\t <-- %d\n", data);
        }
        else
        {
            printf("\n");
        }
    }
}

int main(void)
{
    hash_table *ht = init_ht(SIZE);

    srand(time(NULL));
    int i;
    for(i=0; i<10; i++)
    {
        hash_add(rand()%1000, ht);
        sleep(1);
    }
    show(ht, -1, -1);

    int n;
    while(1)
    {
        scanf("%d", &n);
        if(n > 0)
        {
            hash_add(n, ht);
            show(ht, -1, -1);
        }
        else
        {
            if(hash_del(-n, ht))
                show(ht, -1, -1);
            else
                printf("查无此人!\n");
        }

    }

    return 0;
}